package com.gxc.heap;

import java.util.Random;

/**
 * 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 */
public class FindKthLargest {

    public static void main(String[] args) {
        System.out.println(5 + new Random().nextInt(1));
    }

    public int findKthLargest(int[] nums, int k) {
        return handle(0, nums.length-1, nums, nums.length - k);
    }

    public int handle(int left, int right, int[] nums, int index) {
        int randomN = getRandom(left, right);
        int cur = quickSort(left, right, randomN, nums);
        if (cur == index) return nums[cur];

        if (cur > index) {
            return handle(left, cur-1, nums, index);
        } else {
            return handle(cur+1, right, nums, index);
        }
    }

    private int quickSort(int left, int right, int target, int[] num) {
        int l = left-1;
        int pivotValue = num[target];
        swap(target, right, num);
        int i = left;
        for (; i < right; i++) {
            if (num[i] < pivotValue) {
                l++;
                swap(i, l, num);
            }
        }
        l++;
        swap(l, right, num);
        return l;
    }

    private void swap(int i, int j, int[] num) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }


    private int getRandom(int left, int right) {
        return left + new Random().nextInt(right - left+1);
    }

    int quickselect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }
    public int findKthLargest2(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }

}
